/****************************************************************************
* Lights Game Solution Finder
* By: Sean Zhang
* At: Apr, 2007
*  @: sea_sky_heart@yahoo.com.cn
*  H: http://360.yahoo.com/sea_sky_heart
*
* Reference:
*   http://dev.csdn.net/author/gz80/639df7d1a4694d279812b185efe5147f.html
*****************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define   ABS(x)   (x   <   0   ?   -(x)   :   (x))
#define   EPS   0.00001
#define   TRUE     1
#define   FALSE   0

void  WriteSolution(int   **a,int   n,int   *x) {
    int   j,k;

    for(j=0;j<n;j++)   {
        for(k=0;k<n+1;k++)   {
            printf("%d ",a[j][k]);
        }
        printf(" | %2d\n",x[j]);
    }
    printf("\n");
}


int GSolve(int   **a,int   n,int   *x) {
    int   i,j,k,maxrow;
    int   tmp;

    for(i=0;i<n;i++)   {
        /*   Find   the   row   with   the   largest   first   value   */
        maxrow   =   i;
        for(int r=i+1; r<n; r++)   {
            if(ABS(a[r][i])   >   ABS(a[maxrow][i]))
                maxrow   =   r;
        }

        /*   Swap   the   maxrow   and   ith   row   */
        for(int c=i; c<n+1; c++)   {
            tmp   =   a[i][c];
            a[i][c]   =   a[maxrow][c];
            a[maxrow][c]   =   tmp;
        }

        /*   Singular   matrix?   */
        if(ABS(a[i][i])   <   EPS){
            break;
            // XXX: return(FALSE);
        }

        // DEBUG: WriteSolution((int **)a,n,x);
        /*   Eliminate   the   ith   element   of   the   jth   row   */
        for(int r=i+1; r<n; r++)   {
           for(int c=n; c>=i; c--)   {
               //XXX: a[r][c] = a[r][c]  - a[i][c]   *   a[r][i]   /   a[i][i];
               a[r][c] = (a[r][c]  + a[i][c]   *   a[r][i]   /   a[i][i])%2;
           }
        }
        // DEBUG: WriteSolution((int **)a,n,x);
    }

    /*   Do   the   back   substitution   */
    srand( time(NULL) );
    for(int r=n-1; r>=0; r--)   {
        tmp   =   0;
        for(int c=r+1; c<n; c++)
              tmp   +=   a[r][c]   *   x[c];
        //XXX: x[r]   =   (a[r][n]   -   tmp)   /   a[r][r];
        if(a[r][r] == 0)
             x[r] = rand() & 0x01;
        else
	    x[r]   =   (a[r][n]   +   tmp)%2;
    }

    return(TRUE);
}



int main(int   argc,char   **argv) {
    int N = 5;
    int n   =   25;
    int **a ;
    int *x ;

    // build matrix
    x = (int *)malloc(n*sizeof(int));

    a   =   (int   **)malloc((n)*sizeof(int   *));
    for   (int i=0;i<n;i++)
          a[i]   =   (int   *)malloc((n+1)*sizeof(int));

    for(int i=0;i<n;i++){
       x[i] = 0;
       a[i][n] = 1;
    }

    for(int c=0;c<n;c++){
        int ri = (int) c/N;
        int ci = c%N;
        for(int r=0;r<n;r++){
            a[r][c] = 0;
        }

        a[c][c] = 1;
        if(ci<N-1 && c+1 < n ) a[c+1][c] = 1;
        if(ci>0 ) a[c-1][c] = 1;

        if(ri>0)   a[c-N][c] = 1;
        if(ri<N-1 && c+N < n) a[c+N][c] = 1;
    }

    // solve matrix
    printf("Problem:\n");
    WriteSolution(a,n,x);
    GSolve(a,n,x);
    printf("Solution:\n");
    WriteSolution((int **)a,n,x);

    return 0;
}


